/*
题目:检查数组是否存在有效划分
给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。

如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：

    子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
    子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
    子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。

如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。

https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array
 */
public class ValidPartition {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        if (n == 1)  return false;

        // 表示到 i 元素时能否构成有效划分
        boolean[] dp = new boolean[n];
        dp[1] = nums[0] == nums[1];

        if (n == 2)  return dp[1];
        dp[2] = (nums[0] == nums[1] && nums[1] == nums[2]) || (nums[2] == nums[1] + 1 && nums[2] == nums[0] + 2);

        for (int i = 3; i < n; i ++) {
            dp[i] = (dp[i - 2] && nums[i] == nums[i - 1]) ||
                    (dp[i - 3] && nums[i] == nums[i - 1] && nums[i] == nums[i - 2]) ||
                    (dp[i - 3] && nums[i] == nums[i - 1] + 1 && nums[i] == nums[i - 2] + 2);
        }

        return dp[n - 1];
    }
}
